import java.util.HashMap;
import java.util.Map;

public class Test {
    /**
     * 力扣904(水果成篮)
     * 算法:滑动窗口
     * */

    public int totalFruit(int[] fruits) {//使用哈希表模拟，但频繁调用时间复杂度较高
        Map<Integer, Integer> hash = new HashMap<>();
        int n=fruits.length;
        int len=0;
        for(int left=0,right=0;right<n;right++){
            int variety = fruits[right];//标记种类(进入窗口)
            hash.put(variety,hash.getOrDefault(variety,0)+1);//存在就任然是之前的数量加1，不存在就原本0的基础上加一
            while(hash.size()>2){//判断
                int out=fruits[left++];
                hash.put(out,hash.get(out)-1);//出窗口(找出那个值减一即可)
                if(hash.get(out)==0){//若当前种类数量为0的时候就移除当前种类
                    hash.remove(out);
                }
            }
            //更新结果
            len=Math.max(len,right-left+1);
        }
        return len;
    }
    public int totalFruit1(int[] fruits) {//使用数组模拟，耗时方面会比哈希表低很多

        int n=fruits.length;
        int[] hash = new int[n+1];
        int len=0;
        for(int left=0,right=0,kids=0;right<n;right++){
            int variety = fruits[right];//标记种类
            if(hash[variety]==0){//维护水果种类，若为0进行加加
                kids++;
            }
            hash[variety]++;//进入窗口
            while(kids>2){//判断
                int out=fruits[left++];
                hash[out]--;//出窗口(找出那个值减一即可)
                if(hash[out]==0){//若当前种类数量为0的时候就移除当前种类
                    kids--;
                }
            }
            //更新结果
            len=Math.max(len,right-left+1);
        }
        return len;
    }
    public int totalFruit2(int[] fruits) {
        int n=fruits.length;
        int len=0;
        for (int i = 0; i < n; i++) {
            Map<Integer,Integer> hash=new HashMap<>();
            for (int j = i; j < n; j++) {
                int fruit=fruits[j];
                hash.put(fruit,hash.getOrDefault(fruit,0)+1);
                if(hash.size()<=2){
                    len=Math.max(len,j-i+1);
                }
            }
        }
        return len;
    }

    public static void main(String[] args) {
        int[] fruits = {1,2,3,2,2};
        Test test = new Test();
        System.out.println(test.totalFruit2(fruits));//输出两种水果种类的最长数组长度
    }
}
